Solving Large-Scale Robust Stability Problems by Exploiting the Parallel Structure of Polya's Theorem

摘要

In this paper, we propose a distributed computing approach to solvinglarge-scale robust stability problems on the simplex. Our approach is toformulate the robust stability problem as an optimization problem withpolynomial variables and polynomial inequality constraints. We use Polya'stheorem to convert the polynomial optimization problem to a set of highlystructured Linear Matrix Inequalities (LMIs). We then use a slight modificationof a common interior-point primal-dual algorithm to solve the structured LMIconstraints. This yields a set of extremely large yet structured computations.We then map the structure of the computations to a decentralized computingenvironment consisting of independent processing nodes with a structuredadjacency matrix. The result is an algorithm which can solve the robuststability problem with the same per-core complexity as the deterministicstability problem with a conservatism which is only a function of the number ofprocessors available. Numerical tests on cluster computers and supercomputersdemonstrate the ability of the algorithm to efficiently utilize hundreds andpotentially thousands of processors and analyze systems with 100+ dimensionalstate-space. The proposed algorithms can be extended to perform stabilityanalysis of nonlinear systems and robust controller synthesis.